package com.algorithm;

import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

public class Sort {

    public static void main(String[] args){
        Random rand = new Random();
        int size = 1000000;
        int numRange = 10000000;
        int[] input = new int[size];
        int index = 0;



        while(index < input.length){

            input[index] = rand.nextInt(numRange);

            index ++;
        }
        Sort sort = new Sort();

        long start = System.currentTimeMillis();
        //sort.mergeSort(input);

        Arrays.sort(input);
        long end = System.currentTimeMillis();

        System.out.println(end - start);




    }

    private int[] mergeSort(int[] input){

        if(input.length <= 1){
            return input;
        }

        mergeSort(0,input.length-1,input);
        return input;

    }

    private void mergeSort(int startIndex,int endIndex,int[] input){

        if(endIndex == startIndex){
            return;
        }

        int mid = (startIndex + endIndex) / 2;

        mergeSort(startIndex,mid,input);
        mergeSort(mid + 1, endIndex,input);

        int[] tmp = new int[endIndex - startIndex + 1];
        int index = 0;
        int point1 = startIndex;
        int point2 = mid + 1;

        while(point1 <= mid || point2 <= endIndex){

            if(point1 > mid){
                tmp[index ++] = input[point2++];
                continue;
            }
            if(point2 > endIndex){
                tmp[index ++] = input[point1++];
                continue;
            }

            if(input[point1] < input[point2]){
                tmp[index ++] = input[point1 ++];
            }else{
                tmp[index ++] = input[point2 ++];
            }


        }

        for(int i = 0; i < tmp.length;i ++){
            input[startIndex + i] = tmp[i];
        }



    }
}
